package sortedListToBST

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
type ListNode struct {
	Val  int
	Next *ListNode
}

/**
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
给定的有序链表： [-10, -3, 0, 5, 9],
*/
func sortedListToBST(head *ListNode) *TreeNode {
	num := 0
	tempHead := head
	// 计算链表长度
	for tempHead != nil {
		num++
		tempHead = tempHead.Next
	}
	// 定义函数：根据下标构建当前树
	var dfsBuildTree func(index int) *TreeNode
	// 递归构建数
	dfsBuildTree = func(index int) *TreeNode {
		// 防止越界
		if index > num {
			return nil
		}

		root := &TreeNode{}
		// 当前结点的左子树下标为 index * 2
		root.Left = dfsBuildTree(index * 2)
		if head == nil {
			return nil
		}
		root.Val = head.Val
		head = head.Next
		// 当前结点的左子树下标为 index * 2 + 1
		root.Right = dfsBuildTree(index*2 + 1)
		return root
	}
	return dfsBuildTree(1)
}
